# 139. 单词拆分
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)

        @cache
        def dfs(i: int):
            for j in range(i - 1, -1, -1):
                if s[j: i] in wordDict and dfs(j):
                    return True
            return i == 0

        return dfs(n)

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)

        @cache
        def dfs(i: int, j: int):
            if i < 0:
                return j == 0
            if s[i:j] not in wordDict:
                return dfs(i - 1, j)
            return dfs(i - 1, j) or dfs(i - 1, i)

        return dfs(n - 1, n)
